/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
/*
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 让较长链表先走到和短链表相同的起始位置再逐个进行判断
        size_t lenA = 0, lenB = 0;
        ListNode* curA = headA, *curB = headB;
        while(curA != nullptr){
            ++lenA;
            curA = curA->next;
        }
        while(curB != nullptr){
            ++lenB;
            curB = curB->next;
        }
        int diflen;  // 长度差
        if(lenA > lenB){
            diflen = lenA-lenB;
            curA = headA;
            curB = headB;
        }else{
            diflen = lenB-lenA;
            curA = headB;
            curB = headA;
        }
        while(diflen--)
            curA = curA->next;
        while(curA && curB && curA != curB){
            curA = curA->next;
            curB = curB->next;
        }
        return curA;
    }
*/

    /*** 
    当链表相交时分两种情况：
       *  1. A, B长度相等， 两个链表同时向后遍历然后找到交点返回；
       *  2. A, B长度不相等，先分别进行遍历，较短的链表会先到达null，然后从另一链表的头开始遍历，当长链表也遍历到null时候也移到短链表头开始遍历！！此时，原较短链表指针，现在指向正好是两链表长度差的位置(两指针指向的后续长度相等且等于短链表长度)，而原长链表指针位于锻炼表head，两指针同时继续向后遍历 等价于情况 1.
       *
    不相交时，两个指针分别遍历两个链表，最后退出循环返回null
    ***/

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr)
            return nullptr;
        ListNode* curA = headA, *curB = headB;
        while(curA != curB){
            curA = (curA == nullptr) ? headB : curA->next;
            curB = (curB == nullptr) ? headA : curB->next;
        }
        return curA;
    }
};